package com.cute.leetcode.editor.cn.my;

import java.util.Arrays;

/**
 *  归并排序
 *  Array_a [1,4,7,8, 3,6,9]  i=0 j=4
 *
 *  Array_b [0,0,0,0,0,0,0]  k=0
 *
 *  比较 i 和 j 比较 如果 i<j   则把Array_a i 的值复制到 Array_b 对应的位置  然后 i+1; k+1;
 *
 *  比较 i 和 j 比较 如果 i>j   则把Array_a j 的值复制到 Array_b 对应的位置  然后 k+1; j+1;
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] array={1,4,7,8,3,6,9};
        sort(array,0,array.length-1);
        System.out.println(Arrays.toString(array));
    }
    public static void sort(int[] array,int left,int right){
        if(left<right){
            int middle=(left+right)/2;
            sort(array,left,middle);
            sort(array,middle+1,right);
            merge(array,left,middle,right);
        }
    }

    /**
     *
     * @param arr 排序数组
     * @param left 数组最左边下标
     * @param middle 数组中间位置下标
     * @param right 数组最右位置下标
     */
    public static void merge(int[] arr, int left, int middle, int right){

        /**因为每次切割后左边下标都是（left,middle），右边数组的下标是(middle+1,right)
         * 所以左边数组的元素个数就是middle - left + 1
         * 右边的数组元素个数就是right - middle
         * **/
        final int leftArrayLength = middle-left+1;//切割后左边数组的数据长度
        final int rightArrayLength = right-middle;//切割后右边数组的数据长度
        /**创建两个新数组将切割后的数组分别放进去，长度加1是为了放置无穷大的数据标志位**/
        final int[] leftArray = new int[leftArrayLength+1];//加一操作是增加无穷大标志位
        final int[] rightArray = new int[rightArrayLength+1];//加一操作是增加无穷大标志位
        //两个循环将数据添加至新数组中
        /**左边的数组下标是从left到middle**/
        /**遍历左边的数组*/
        for (int i = 0; i < leftArrayLength; i++) {
            leftArray[i] = arr[left+i];
        }
        for (int i = 0; i < rightArrayLength; i++) {
            rightArray[i] = arr[middle+1+i];
        }

        //将最大的正整数放在两个新数组的最后一位
        leftArray[leftArrayLength] = Integer.MAX_VALUE;
        rightArray[rightArrayLength] = Integer.MAX_VALUE;

        int i = 0,j = 0;
        //谁小谁放在前面
        for (int k = left; k <= right; k++) {
            if (leftArray[i]<=rightArray[j]) {
                arr[k] = leftArray[i];
                i = i+1;
            } else {
                arr[k] = rightArray[j];
                j = j+1;
            }
        }


    }

    public void swap(int[] array,int i,int j){
        int temp=array[i];
        array[i]=array[j];
        array[j]=temp;
    }

    public static void print(int[] array){
        for (int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
    }
}
